The present invention relates to information handling systems (IHSs) used in    telecommunications networks, and more particularly to managing data forwarding systems (e.g. bridges) while suppressing loops in telecommunications networks.
As the value and use of information continues to increase, individuals and businesses seek additional ways to process and store information. One option is an IHS. An IHS generally processes, compiles, stores, and/or communicates information or data for business, personal, or other purposes. Because technology and information handling needs and requirements may vary between different applications, IHSs may also vary regarding what information is handled, how the information is handled, how much information is processed, stored, or communicated, and how quickly and efficiently the information may be processed, stored, or communicated. The variations in IHSs allow for IHSs to be general or configured for a specific user or specific use such as financial transaction processing, airline reservations, enterprise data storage, or global communications. IHSs may include a variety of hardware and software components that may be configured to process, store, and communicate information and may include one or more computer systems, data storage systems, and networking systems, such as a data forwarding system.
FIG. 1 is a block diagram of a Local Area Network (LAN) which is a type of a telecommunications network. The LAN interconnects a number of stations 110 which can be computers, printers, or other types of stations. The LAN is segmented into LAN segments 120.1, 120.2, . . . interconnected by data forwarding systems 130. In this example, each data forwarding system is a bridge. Each LAN segment 120.x is a separate LAN. Segmentation can be done for various reasons, e.g. historical (to interconnect pre-existing LAN segments into a single LAN), organizational (to allow different LAN segments to be managed by different organizations), security checking (performed by bridges), reduce collisions since different LAN segments are different collision domains, and possibly others. See e.g. A. S. Tanenbaum, Computer Networks, 4th ed. 2003, section 4.7, incorporated herein by reference.
When a bridge 130 receives a data frame 200 (FIG. 2), the bridge must decide on which port (“outbound port”) the frame must be forwarded. These decisions are made based on the bridge's filtering database (FDB) 204 stored in the bridge's memory. Data frame 200 contains a source address 206S and a destination address 206D (sometimes called MAC addresses (MAC stands for Media Access Control) or layer-2 addresses (L2 addresses)). The FDB 204 specifies the outbound port or ports for destination address 206D. For example, for bridge 130.1, the database 204 may specify the port P2 for destination addresses on LANs 120.7 and 120.6; port P3 for destination addresses on LAN 120.1; and port P1 for other destination addresses.
The bridge will not forward a frame on a port on which the frame was received. For example, if bridge 130.1 receives a frame on port P1 and the outbound port is also P1, the bridge discards the frame. Otherwise, the bridge forwards the frame on the outbound port (unless security or other restrictions apply; see for example IEEE (Institute of Electrical and Electronic Engineers) Standard 802.1D™-2004 incorporated herein by reference; the invention is not limited to bridges complying with this standard however.)
If the destination address 206D is not in database 204, the bridge floods the frame, i.e. forwards the frame on all the ports except the port on which the frame was received (unless restrictions apply).
The database 204 can be populated by an administrator (a human), but can also be dynamically learned by the bridge from the data frames' source addresses. For example, if bridge 130.1 receives a data frame on port P1 with a source address having a value A1, the bridge will associate A1 with the port P1, and will enter this association into database 204. The database will show the port P1 as the outbound port for address A1. Clearly, when the LAN topology changes, e.g. stations 110 or 130 are disconnected or moved, the filtering database 204 should be flushed entirely or partially. This however leads to flooding, and hence disrupts network traffic.
A bridge may also have an ARP (Address Resolution Protocol) cache 220 (FIG. 2) for forwarding data frames for which the bridge does not have a MAC address in FDB 204, if the data frame contains a network destination address 230D (also called L3 or Layer-3 address, e.g. an IP address). As shown in FIG. 2, a data frame's layer-2 payload may include Layer-3 destination address 230D and Layer-3 source address 230S. If the data frame's MAC destination address 206D is the bridge's address, and the frame's L3 destination address 230D is present in the bridge's ARP cache 220, then the bridge will forward the frame to the corresponding MAC address in the ARP cache (unless restrictions apply). The MAC address can be looked up in FDB 204 to determine the outbound port. The MAC address may be that of the final destination (the same as identified by Layer-3 address 230D), or may be of another bridge that can forward the frame to the final destination.
The ARP cache is populated by an administrator or an automatic learning process in which the bridge may broadcast an inquiry about a layer-3 address to obtain the corresponding MAC address; the MAC address is provided by the address owner (a station 110 or bridge 130) or another bridge that can forward data frames to the layer-3 address.
To improve reliability, the LAN may include redundant paths between different LAN segments. For example, in FIG. 1, LAN segments 120.7 and 120.3 are interconnected by a path through bridges 130.1, 130.2, and by an alternate path through bridges 130.6, 130.4, 130.2. If one of these paths fails, the other path is available. However, if both paths are active at the same time, the segment 120.3 may receive duplicate copies of data frames because both bridges 130.1, 130.6 may forward the same data frame on their respective ports P1, P2, and bridge 130.4 may forward its copy of the frame further on. Also, a broadcast frame may circulate indefinitely around the LAN. Therefore, the bridges block redundant paths (i.e. eliminate “loops”) by deactivating their ports as needed. (In this disclosure, we say that a loop exists if data can undesirably reach the same destination over different paths, or can circulate around the LAN; elimination of such conditions is referred to as loop elimination.)
To study LAN loops (i.e. loops created in layer-2 forwarding), it is helpful to represent the LAN in a simplified form (FIG. 3), without the stations 110. Each LAN segment 120 is shown as a link between two or more bridges. (Segment 120.5 is a ring (see FIG. 1) connected to two ports P2′, P2″ on each bridge 130.2, 130.4; in FIG. 3, the two ports are shown as a single port P2 on each bridge.) The loops can be eliminated by bridge 130.6 deactivating its port P2, as shown by a “cut” line 310. The port P2 may or may not remain fully operational for bridge management messages (called Bridge Protocol Data Units or BPDUs in IEEE 802.1D-2004 referenced above). The bridges exchange such messages to detect loops.
An exemplary protocol for eliminating loops in LANs is Rapid Spanning Tree Protocol (RSTP) defined by IEEE 802.1D-2004 in Clause 17. Under RSTP, the bridges activate or deactivate their ports to provide a tree topology on the LAN, i.e. to eliminate loops. When a port is active, it is said to be in Forwarding State. A non-active port's state may be Discarding; in this state the port does not transmit any data other than management data, and any non-management data received on the port are discarded by the bridge. Alternatively, the port may be in Learning state: this state is similar to Discarding, but the received frames are used to populate the filtering database 204 for the port.
Initially all the ports may be Discarding except for the Edge ports, i.e. the ports not directly connected to any other bridge (such as the port P3 of bridge 130.1). The Edge ports can always be Forwarding unless they are disabled (by an administrator for example). The non-management ports exchange BPDUs to determine which ports can become Forwarding. Based on the BPDUs, one bridge is elected as the root bridge for the LAN. (In FIG. 3, bridge 130.2 is the root.) In deciding which ports should be Forwarding, priority is given to ports closest to the root (having the minimum cost of reaching the root).
The RSTP is executed continuously, so that the ports' states can change based on changes in the LAN.
FIGS. 4A-4D illustrate an exemplary network of four bridges 130.1-130.4 connected in a ring. Bridge 130.1 has been elected as the root. Link 120.1 is down or absent, so the corresponding ports P1 and P2 of bridges 130.1, 130.2 are Discarding (possibly disabled), as indicated by “D” in FIG. 4A. The remaining ports of the four bridges are Forwarding as shown by “F”.
Then link 120.1 becomes operational (FIG. 4B). Root bridge 130.1 sends a “Proposal” BPDU on its port P1 to propose activation of this port. The Proposal BPDU shows the cost of reaching the root as zero.
Bridge 130.2 determines from the proposal that its port P2 has a low cost of reaching the root 130.1 and thus should be used in preference to its port P1 (connected to bridge 130.3). Before changing P2 to Forwarding, bridge 130.2 deactivates its other non-edge ports to prevent loops. In particular, the bridge's port P1 becomes Discarding (as shown by “F→D” near P1).
Bridge 130.2 sends an Agreement BPDU to bridge 130.1 (FIG. 4C). Bridge 130.1 changes its port P1 to Forwarding.
Bridge 130.2 sends a Proposal BPDU on its port P2 (on link 120.2) to bridge 130.3 to inform the bridge 130.3 of the topology change caused by activation of link 120.1, and also to determine if port P1 of bridge 130.2 should again become Forwarding.
In this example, bridge 130.3 determines that its port P2 should remain Forwarding. The bridge changes its other non-edge ports (like P1) to Discarding to avoid any loops that may have been caused by the topology change. The bridge sends an Agreement BPDU to bridge 130.2 (FIG. 4D). Bridge 130.2 then changes its port P1 to Forwarding, and flushes its FDB 204 of any entries containing the port P1. The ARP cache is also flushed. The reason is as follows. In a bridge, different ports have different MAC addresses. Therefore, in the ARP cache, the MAC addresses correspond to the ports of final destinations or intermediate bridges. If the topology changes, the path to the final destination or the intermediate bridge may also change, and may terminate at a different port of the final destination or the intermediate bridge. In such a case, the MAC address in the ARP cache should change.
As shown in FIG. 4D, bridge 130.3 sends a Proposal on port P1 to bridge 130.4 over link 120.3, but bridge 130.4 rejects the Proposal. Therefore, bridge 130.3 leaves its port P1 as Discarding. Bridge 130.4 has to flush its FDB 204 of any entries containing the ports P2 and P1. The ARP cache 220 is also flushed.
Bridge 130.1 learns of the topology change and flushes its FDB 204 and ARP cache 220 of any entries related to its port P2. The port states finally stabilize after the link 120.1 activation, but the traffic will remain disrupted for a while as the bridges re-build their FDBs 204 and ARP caches 220.
Much attention has been devoted to the need to reduce flushing and speed up changing of port states to Forwarding. IEEE 802.1D-2004 specifies for example, in section 17.3, that once a port is designated as a Root port (closest to the root bridge), the Root port can transition to Forwarding state without transmitting or receiving messages from other bridges. Situations have been identified in which flushing can be eliminated or reduced. See e.g. U.S. Pre-Grant Patent Publication US 2011/0292833 (Dec. 1, 2011) and V. Jain et al., “Faster flushing with fewer addresses”, Jan. 7, 1999 (discussing an older Spanning Tree Protocol), both incorporated herein by reference. Further improvements in this regard are desirable.